package k3;

import java.util.Comparator;

public class PriorityQueue<A> {
	private DynamicArray<A> array;
	private Comparator<A> comparator;
	private int size=0;
	
	PriorityQueue(Comparator<A> comparator){
		array=new DynamicArray<A>(1);
		array.add(null);//element at index 0 will be not used
		this.comparator=comparator;
	}
	
	/**
	 * put the element in a queue
	 * @param number
	 */
	public void enqueue(A number){
		int child,parent;//indexes to the parent and child in array
		array.add(number);
		child=array.length()-1;
		while(true){
			parent=findParent(child);
			if(parent==-1)break;//has reached the top
			if(comparator.compare(array.get(child),array.get(parent)) <=0)break;//node in its correct position
			swap(child,parent);
			child=parent;//node has moved to its previous parents position
		}
		size++;
	}
	
	/**
	 * take the minimal element from queue
	 * @return
	 */
	public A dequeue(){
		if(size<1)throw new IndexOutOfBoundsException();
		A result=array.get(1);
		int child[];
		int parent;//indexes to the parent and child in array
		int minChild;
		A element=array.removeLast();
		if(isEmpty())array.add(element);
		else{array.set(1, element);}
		parent=1;
		while(true){
			child=findChild(parent);
			if(child==null)break;//0 children, node may remain in place
			minChild=findMinChild(child);
			if(comparator.compare(array.get(parent),array.get(minChild)) >=0)break;//node in its correct position
			swap(parent,minChild);
			parent=minChild;//node has moved to its previous children's position
		}
		size--;
		return result;
	}
	
	public boolean isEmpty(){
		if(array.length()<2 || size<1)return true;//TODO:test
		return false;
	}
	
	/**
	 * find childs parent
	 * @param child index of child
	 * @return index of parent
	 */
	private int findParent(int child){
		int parent=child/2;
		if(parent<1)parent=-1;
		return parent;
	}
	
	/**
	 * find indexes of parent childs
	 * @param parent index of a parent
	 * @return
	 */
	private int[] findChild(int parent){
		if(parent*2>=array.length())return null;
		if(parent*2>=array.length()-1)return new int[] {parent*2};
		return new int[] {parent*2,parent*2+1};
	}
	
	/**
	 * find index of a child with minimal value from childs
	 * @param child array with indexes of childs
	 * @return index of minimal child
	 */
	private int findMinChild(int[] child){
		if(child.length==1)return child[0];
		if(comparator.compare(array.get(child[0]),array.get(child[1])) >=0)return child[0];
		return child[1];
	}
	
	/**
	 * swap elements in array at those indexes
	 * @param index1
	 * @param index2
	 */
	private void swap(int index1,int index2){
		A temp=array.get(index1);
		array.set(index1, array.get(index2));
		array.set(index2, temp);
	}
	
	public int getSize(){
		return size;
	}
}
